In most modern computer systems, when a program is executing, it frequently attempts to access data or code which resides somewhere in the system (that is, in some level of the cache/main store/Direct Access Storage Device (DASD) storage hierarchy or even at another node in a distributed system network). For the most primitive system, consider what the program must understand in order to make this access.
Where is the data (or code)? The location will generally determine what kind of address must be used for the access (e.g. main storage address of 24 bits, or sector address on a disk track, or node address in a network). The location will also determine what kinds of instructions must be used to accomplish the access (e.g. Load/Store/Branch for main storage accesses, channel command words for disk accesses, communication protocols for network accesses). PA0 Is this data shared with other program executions? If it is, the access cannot proceed unless certain locks are held. If the changes which this program is about to make to data are not to be seen by others at this time, the Store instruction must be to some private address. PA0 Is this data to be recoverable? If it is, some "journalling" strategy must be implemented so that a consistent prior state of the data can be retrieved when necessary. PA0 If the program is to be generally applicable the accesses would be very slow, even for the most frequent occurrences of "trivial, safe" requests, namely, for private, unrecoverable data in main storage. PA0 If the program were to perform well it would be locked into one accessing mode, so that it would not run correctly against data with different characteristics. PA0 The program would be complex, large and prone to error. PA0 Relocate architectures generally allow private, unrecoverable, nonpersistent data and programs to be addressed uniformly, with an address size of 16 to 32 bits --(usually adequate for temporary computational requirements). When these architectures are implemented with proper "look-aside" hardware, the vast majority of such accesses are accomplished at cache or main storage speeds. Only when this look-aside hardware fails (less than one in one hundred attempts) does the system pay the cost of accessing the relocation table structure. And only when the relocation tables fail (i.e. the data is not in main storage) does the system pay the significant "page fault" overhead. Thus the penalties are paid only when they are really necessary, which is surely the goal of a good architecture and implementation. PA0 When the data is to persist beyond this execution of this program, most modern systems require that, instead of Load/Store/Branch instructions, access be made by explicit requests to software-implemented "access methods." These access methods generally support data which are organized into certain defined aggregates, called "records" and "files." The "instructions" to access are usually called "read/write" or "get/put." PA0 When the data is to be shared or recovered, most modern systems require that explicit requests be made to softwareimplemented "data-base subsystems." These accesses are generally much slower than those for access methods, not only because of the additional functions of lock and journal management, but also because the kinds of aggregates which these subsystems support (e.g. relations, hierarchies) are themselves more complex. PA0 The IBM System/38 has gone farther than most systems in providing at least a uniform addressing structure for all data. But it has done this at the cost of making all addresses very large, many accesses very slow, much storage and hardware required to implement the architecture, and has not yet provided a uniform approach to sharing or recovery.
Suppose, in this very primitive system, the program was in fact required to make these distinctions at each access. Then the following would result:
Modern systems have addressed these problems in varying degrees. For instance:
This data is not shared or recoverable. It may in fact be in main storage (in some buffer area). But for every access, the program must pay the overhead of these explicit "read/write" calls. Thus access methods, when suitably defined have resulted in programs which are less complex and more generally usable than in primitive systems, but the performance of these accesses are uniformly poorer than Load/Store, and the data accessed must have been structured into the appropriate aggregate type.
Again, the data may in fact be more simply structured and in a buffer in main storage, but the overhead must be paid on every access request.
Some systems support the recovery of non-persistent data with a facility called "checkpointing." Now the programmer who wishes to write a recoverable application must deal with three different facilities--checkpointing for computational data, explicit backup for files, and "commit" instructions for data base.
Various techniques are known in the art whereby a number of computer programs, whether executed by a single essential processing unit or by a plurality of such a processing units, share a single memory. The memory being shared by programs in this manner requires an extremely large parent storage capacity, which capacity is often much larger than the actual capacity of the memory. If, for example, a system employs a 32-bit addressing scheme, 2.sup.32 addressable bytes of virtual storage are available. This virtual storage space is conventionally thought of as being divided into a predetermined number of areas or segments each of which is in turn divided into pages with each page consisting of a predetermined number of lines each in turn having a predetermined number of bytes. Thus segment and page designations or addresses assigned to virtual storage are arbitrary programming designations and are not actual locations in main storage. Therefore, virtual segments and pages are usually randomly located throughout main storage and swap in and out of main storage from backing store as they are needed.
The random location of segments and pages in main storage necessitates the translation of virtual addresses to actual or real addresses using a set of address translation tables that are located in main storage conventionally referred to as page frame tables. In a large virtual system a great many such address translation tables are employed. These may be organized in a number of different ways. The essential feature of any such organization is that the particular virtual address must logically map to a memory location in said tables which will contain the real address for said virtual address (if one exists).
Functionally, the operation of such address conversion tables is as follows: the high order bits of the particular virtual address are used to access a specific section of said translation tables, which relate to a particular frame or segment, where upon a search is then performed on the lower bits to see if a particular virtual address is contained therein and, if so, what real address is associated therewith. Each page table pointed to by a virtual frame address contains the real locations of all of the pages in one of the frames. Therefore if a particular frame is divided into for example, 16 pages there would be 16 page tables, for each frame, and a separate frame table which would have the entries pointing to a particular set of individual page tables. It should be understood that the above description is generalized in nature and that there are many different ways of organizing the address conversion utilizing the page tables, as well as the means for addressing same, starting with the CPU produced virtual address. In the subsequent description of the preferred form of the invention as set forth and disclosed in the embodiment there will be a detailed description of the hash address tables (HAT) and the inverted page tables (IPT) which, in essence, are functionally organized as set forth above.
When making the actual address translation, regardless of the details of the overall system organization and use of the page tables, the proper entry point into the page-frame tables is made and the page tables are accessed using the presented virtual address as the argument and, usually after a plurality of memory accesses, the desired entry in the page tables is found. At this point a check is usually made to determine if all system protocols have been followed and if so, the real address of the requested page in memory is accessed from the page table. The byte portion of the virtual address is essentially a relative address and is the same in the virtual page as in the real page whereby once the desired real page address portion of the virtual address has been translated, the byte portion is concatenated onto the real page address location to provide the real byte address in main storage.
As is well known in current virtual memory systems, in order to avoid having to translate a virtual address each time the memory is accessed, current translations of recently used virtual addresses to real addresses are retained in a special set of rapidly accessible tables or high speed memories referred to as Directory Look-Aside Tables (DLAT) or Translation Look-Aside Buffers (TLBs) as used in the present invention. These tables or buffers are conventionally special high speed or rapidly accessible memories which may be accessed much faster than the previously described page frame tables whereby frequently used virtual addresses may be stored in this table and accessed very rapidly with the resultant saving of a great deal of execution time within the computer. The efficiency of such TLB address translation systems is predicated upon the fact that, subsequent to the first access to a particular virtual page, there will be a great many accesses to the same page during a given program execution. As indicated above, even though subsequent accesses are to different lines and bytes within a page, the virtual to real page address translation is the same for that page regardless of which line or byte is being addressed.
The use of the TLBs significantly reduces the number translations that must be made (in the page frame tables) and thus has a considerable effect on the performance of the overall virtual memory system.
As stated previously, virtual memory systems have been known in the computer arts for many years. It is also well known that the virtual addresses must be translated into real addresses via some sort of relocation or address translation means wherein the translatability of the virtual address into the real memory address must be assured. While it would be impossible to list all patents and articles relating to this sbject, the following prior art is intended to be exemplary of typical address translation mechanisms and represents the closest prior art known to the inventors.
U.S. Pat. No. 3,828,327 of Berglund et al describes a prior storage control technique for extending the memory by means of adding a high order bit to the address which high order bit is not part of the program apparent address but is controlled by the different system modes, such as interrupt mode, I/O mode, etc. This patent relates to a memory extension system but is provided together with appropriate address translation hardware. U.S. Pat. No. 4,042,911 of Bourke et al also discloses a system for extending main storage and explicitly includes address translation means therewith. Neither of these two patents disclose the virtual address expansion concept nor the provision of special lock bits in both the TLBs and page frame tables.
An article entitled "The 801 Minicomputer," by George Radin, published in ACM SIGPLAN NOTICES, Vol. 17, No. 4, Apr. 1982, pages 39-47, includes a general description of an experimental computer whose operational characterisitics depend to a large extent on a very fast memory subsystem in which the present relocation mechanism would have particular utility.
U.S. Pat. No. 4,050,094 of Bourke et al discloses a memory organization including an address relocation translator which includes among other things stack segmentation registers. The particular segmentation registers disclosed in this patent are for the purpose of storing a real assigned address of a physical block in the main memory rather than for storing an expanded virtual address as utilized with the present invention.
U.S. Pat. 4,251,860 of Mitchell et al, discloses a memory addressing system including virtual addressing apparatus for implementing a large virtual address memory. The patent describes a splitting of virtual address into a segment and offset portion however, the segment portion and associated segment registers are used as a convenient way of splitting the address and do not operate in any analogous manner to the adddress translation scheme of the present invention.
U.S. Pat. 4,037,215 of Birney et al, discloses a system very similar to that of the previously referenced U.S. Pat. No. 4,050,094, in that a series of segmentation registers are utilized for pointing to specific real memory blocks. This patent additionally shows the use of `read only` validity bits tied into the specific segmentation registers. These bits have little analogy to the special purpose lock bits provided in the hardware of the present relocation mechanism.
U.S. Pat. No. 4,077,059 of Cordi et al, discloses a hierarchical memory system which includes the provision of special controls to facilitate journalling and copyback. A plurality of dual memories is involved in this patent wherein the current version of data is kept in one of the memories and changes are noted in the other to facilitate subsequent journalling and copyback operations. The hardware and controls of this patent bear little resemblance to the lock bit system of the present invention.
U.S. Pat. No. 4,053,948 of Hogan et al, discloses an address translation system in which special provisions including a counter are included with each entry in a Directory Look-Asid Table (DLAT).
U.S. Pat. No. 4,218,743 of Hoffman et al is exemplary of a number of patents listed below which relate to the IBM System/38 relocation architecture. This particular patent illustrates a simplification of the manner in which I/O handles addressing in a virtual storage computer system. Other patents related to the subject of the virtual storage system are: U.S. Pat No.4,170,039, 4,251,860, 4,215,402.
U.S. Pat. No. 4,020,466 of Cordi et al also discloses a memory system which incorporates a special facilities to facilitate journalling and copyback procedures. The patent has no relationship to the locking bit control means of the present invention.
U.S. Pat. No. 3,942,155 of Lawlor discloses a form of segment partitioning in a virtual memory system, however, the segmenting used in this patent is quite different from the segmenting operation of the present invention which is utilized to expand the virtual address.
U.S. Pat. No. 4,215,402 is cited as exemplary of the use of various hashing schemes for accessing a virtual memory translation mechanism